package com.chj.jz.dp.class05;

public class Code01_CoinsInALineIII {
	/**
	 * @param values:
	 *            a vector of integers
	 * @return: a boolean which equals to true if the first player will win
	 */
	public static boolean firstWillWin(int[] values) {
		int n = values.length;
		int[][] dp = new int[n][n];
		int i, j, len;
		// 初始化
		for (i = 0; i < n; i++) {
			dp[i][i] = values[i];
		}

		for (len = 2; len <= n; len++) {
			for (i = 0; i <= n - len; i++) {
				j = i + len - 1;
				dp[i][j] = Math.max(values[i] - dp[i + 1][j], // 如果先手取i，那么dp[i][j] =
																// values[i]-dp[i+1][j]，因为values[i+1]~values[j]是后手赢先手的分数，所以此时先手选择values[i]和它做差；
						values[j] - dp[i][j - 1]);// 先手取j=i+l，那么dp[i][j] = values[j]-dp[i][j-1]
			}
		}
		// 判断差值是否大于零便能知道赢了输了
		return (dp[0][n - 1] >= 0);
	}

	public static void main(String[] args) {
		{
			int[] arrK = new int[] { 3, 2, 2 };
			System.out.println(firstWillWin(arrK));
		}
		{
			int[] arrK = new int[] { 1, 20, 4 };
			System.out.println(firstWillWin(arrK));
		}
	}
}
